/*
 * BuddySystem.cc
 *
 *  Created on: Feb 8, 2012
 *      Author: marc
 */

#include "BuddySystem.h"
#include <iostream>

#include <stdexcept>

#include "asserts.h"

using namespace std;

BuddySystem::BuddySystem() :
	Allocator("BuddySystem") {
	//cout << "BS INIT" << endl;
	init = -1;
}

const Area* BuddySystem::alloc(int wanted) {

	require( wanted > 0 );	// minstens "iets",
	require( wanted <= size );	// maar niet meer dan we kunnen hebben.

	if (init == -1) {
		//cout << "BS INIT MEMORY" << endl;
		freeMemory[0] = new Area(0, size);
		init = 1;
	}
	if(wanted <= 0){
		return 0;
	}
	const Area* best = 0;
	//cout << size << " " << minSize << endl;

	for (int i = 0; i < (size / minSize); i++) {
		if (freeMemory[i] == 0) {
			//cout << "freeMemory[" << i << "] " << "nothing here... " << endl;
			continue;
		}
		if (freeMemory[i]->getSize() == wanted) {
			//cout << "freeMemory[" << i << "] " << "found an exact fitting piece" << i << endl;
			best = freeMemory[i];
			freeMemory.erase(i);
			//testMemory();
			return best;
		} else if (freeMemory[i]->getSize() > wanted
				&& (best == 0 || freeMemory[i]->getSize() < best->getSize())) {
			//cout << "freeMemory[" << i << "] " << "better than what we got" << endl;
			if(best != 0){
				free(best);
			}
			best = freeMemory[i];
			freeMemory.erase(i);
		}
		/*else {
			cout << "freeMemory[" << i << "] " << "does not fit" << endl;
		}*/
	}

	if(best == 0){
		return 0;
	}

	int returnSize = getClosestPOT(wanted);
	while(true){
		if(best->getSize() == returnSize || best->getSize() == minSize){
			//testMemory();
			return best;
		}else{
			Area * a2 = new Area(best->getBase()+(best->getSize()/2), best->getSize()/2);
			Area * a1 = new Area(best->getBase(), best->getSize()/2);
			free(a2);
			best = a1;
		}
	}
}

int BuddySystem::getClosestPOT(int num){
	int i = minSize;
	while(i < num){
		i = i*2;
	}
	return i;
}

void BuddySystem::free(const Area * ap){
	int buddyIndex = -1;
	if(ap->getBase() % (ap->getSize()*2) == 0){ //bepalen van locatie buddy in freeMemory
		buddyIndex = (ap->getBase() + ap->getSize())/minSize;
	}else{
		buddyIndex = (ap->getBase() - ap->getSize())/minSize;
	}
	if(freeMemory[buddyIndex] != 0 && freeMemory[buddyIndex]->getSize() == ap->getSize()){ //als buddy vrij is
		//cout << "MERGING" << endl;
		if(ap->getBase() < freeMemory[buddyIndex]->getBase()){
			const Area * newMemBlock = new Area(ap->getBase(), ap->getSize()*2);
			freeMemory.erase(buddyIndex);
			free(newMemBlock);
		}else{
			const Area * newMemBlock = new Area(freeMemory[buddyIndex]->getBase(), freeMemory[buddyIndex]->getSize()*2);
			freeMemory.erase(buddyIndex);
			free(newMemBlock);
		}
	}else{ //geen buddy gevonden
		//cout << "freeing: " << ap->getBase() << "..." << ap->getBase()+ap->getSize() << endl;
		freeMemory[ap->getBase()/minSize] = ap;
	}

}

void BuddySystem::testMemory(){
	//cout << "============= Test memory ===============" << endl;
	int freeSizeLeft = 0;
	for(int i=0;i<100;i++){
		if(freeMemory[i] != 0)
			freeSizeLeft += freeMemory[i]->getSize();
	}
	//cout << "Free size available: " << freeSizeLeft <<endl;
}
